#include <bits/stdc++.h>

using namespace std;
extern int randPartition(int A[],int left,int right);
// nth minimum element
int randSelect(int A[],int left,int right,int K)
{
    if (left==right)
    {
        return A[left];
    }
    int pos=randPartition(A,left,right);
    int M=pos-left+1;
    if (K==M)
    {
        return A[pos];
    }
    if (K<M)
    {
        return randSelect(A,left,pos-1,K);
    }
    else
    {
        return randSelect(A,pos+1,right,K-M);
    }
}
int main_114()
{
    srand((unsigned int)time(nullptr));
    int arr[]={4,-2,5,3,8,6,7,9};
    int len=sizeof(arr)/sizeof(arr[0]);
    for (int i=1;i<=len ;++i )
    {
        printf("The i=%d rank=%d\n",i,randSelect(arr,0,len-1,i));
    }
	return 0;
}
